#include <algorithm>
#include <vector>

using namespace std;

class Item
{
public:
	int* profit = nullptr;
	int* capital = nullptr;


	friend bool operator<(const Item& lhs, const Item& rhs)
	{
		return *lhs.capital < *rhs.capital;
	}

	friend bool operator<=(const Item& lhs, const Item& rhs)
	{
		return !(rhs < lhs);
	}

	friend bool operator>(const Item& lhs, const Item& rhs)
	{
		return rhs < lhs;
	}

	friend bool operator>=(const Item& lhs, const Item& rhs)
	{
		return !(lhs < rhs);
	}
};

class IOP
{
public:
	int findMaximizedCapital(int k, int w, std::vector<int>& profits, vector<int>& capital)
	{
		int n = capital.size();
		
		std::vector<Item> items_vec;
		items_vec.resize(n);
		for (int i = 0; i < n; ++i)
		{
			items_vec.at(i).capital = &capital.at(i);
			items_vec.at(i).profit= &profits.at(i);
		}
		std::sort(items_vec.begin(), items_vec.end());

		std::vector<int> profits_heap;
		int offset = -1;
		while(k>0)
		{
			for (int i = offset + 1; i < n; ++i)
			{
				if (w >= *items_vec.at(i).capital)
				{
					offset++;
					profits_heap.push_back(*items_vec.at(i).profit);
					std::push_heap(profits_heap.begin(), profits_heap.end());
				}
				else
					break;
			}

			if(!profits_heap.empty())
			{
				std::pop_heap(profits_heap.begin(), profits_heap.end());
				w += profits_heap.back();
				profits_heap.pop_back();
			}
			
			k--;
		}

		return w;
	}
};
